package com.atguigu.graph;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
public class Dijkstra {
    public static Node getMinDistanceAndUnselectedNode(HashMap<Node,Integer> distanceMap,HashSet<Node> touchedNodes){
        Node minNode=null;
        int minDistance=Integer.MAX_VALUE;
        for(Map.Entry<Node,Integer> entry: distanceMap.entrySet()){
            Node node=entry.getKey();
            int distance=entry.getValue();
            if(!touchedNodes.contains(node) && distance<minDistance){
                minNode=node;
                minDistance=distance;
            }
        }
        return minNode;
    }
    public static HashMap<Node,Integer> dijkstra1(Node head){
        //从head出发到所有点的最小距离
        //key: 从head出发到达key
        //value:从head出发到达key的最小距离
        //如果在表中，没有T的记录，含义是从Head出发到T这个点的距离为正无穷
        HashMap<Node,Integer> distanceMap=new HashMap<>();
        distanceMap.put(head,0);
        //已经求过距离的节点，存在selectedNodes中，以后再也不碰
        HashSet<Node> selectedNodes=new HashSet<>();
        Node minNode=getMinDistanceAndUnselectedNode(distanceMap,selectedNodes);
        while(minNode!=null){
            int distance=distanceMap.get(minNode);
            for(Edge edge: minNode.edges){
                Node toNode=edge.to;
                if(!distanceMap.containsKey(toNode)){
                    distanceMap.put(toNode,distance+edge.weight);
                }
                distanceMap.put(edge.to,Math.min(distanceMap.get(toNode),distance+ edge.weight));
            }
            selectedNodes.add(minNode);
            minNode=getMinDistanceAndUnselectedNode(distanceMap,selectedNodes);
        }
        return distanceMap;
    }
}
